package 数据结构和算法入门计划8月开始;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
// https://www.nowcoder.com/practice/04a5560e43e24e9db4595865dc9c63a3?tpId=188&&tqId=38595&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking
public class NC15求二叉树的层序遍历0821 {



      public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
      }


    public class Solution {
        /**
         *
         * @param root TreeNode类
         * @return int整型ArrayList<ArrayList<>>
         */
        public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
            // write code here
            ArrayList<ArrayList<Integer>> res = new ArrayList<>();
            if(root == null) {
                return res;
            }
            // 队列保存每一层所有结点
            Queue<TreeNode> queue = new LinkedList<>();
            // 先放入根节点
            queue.offer(root);
            while(!queue.isEmpty()) {
                // 收集当前层的所有结点的值
                ArrayList<Integer> list = new ArrayList<>();
                // ·当前层的节点数量
                int count = queue.size();
                // 遍历每一层
                while(count-- > 0) {
                    // 从对头取出节点
                    TreeNode node = queue.poll();
                    // 收集结果
                    list.add(node.val);
                    // 左右节点按顺序加到队尾
                    if(node.left != null) {
                        queue.offer(node.left);
                    }
                    if(node.right != null) {
                        queue.offer(node.right);
                    }
                }
                res.add(list);
            }
            return res;
        }
    }

}
